---
title: "家族"
created: 2025-11-28
tags:
  - 算法
---

# 家族

## 题目 [家族](https://www.luogu.com.cn/problem/P1767)

![[image-3d2b5ee7.png]]

## 思路分析

![[image-b9a81852.png]]

每行可能不一样长 读入恶心 而且还有空格

用`cin >> s`来读取字符串时，`cin`会自动忽略任何空白字符，包括空格、制表符和换行符。这意味着`cin >> s`在遇到第一个非空白字符之前不会停止读取输入，一旦它读取到非空白字符，它会继续读取直到遇到下一个空白字符为止。因此，使用`cin >> s`读取的字符串中不会包含任何空格或其他空白字符。

这是`cin`使用空白字符作为默认分隔符的结果，这在许多情况下都很有用，比如读取单词或独立的数值。但是，如果你想要读取含有空格的整行文本，就需要使用`getline`函数。`getline`会读取输入直到遇到换行符`\n`为止，并将换行符之前的所有内容（不包括换行符本身）存储到给定的字符串变量中，这就允许字符串中包含空格。

例如，如果你的输入是一行文本，你想要完整地读取这一行（包括其中的空格），你应该这样做：

```cpp
#include <iostream>
#include <string>
using namespace std;

int main() {
    string line;
    getline(cin, line);
    cout << line << endl; // 这将打印出包含空格的整行文本
    return 0;
}
```

在处理混合类型的输入（即包含数值和字符串的情况）时，如果你先用`cin`读取数值，然后想用`getline`读取字符串，记得在两者之间用一次额外的`getline`来消耗掉数值后面的换行符

如程序中的

```cpp
    cin>>n;
    getline(cin,s);
    for(int i=0;i<n;i++){
        getline(cin,s);
```

判断的时候也要改成

`return x>=0 && x<=n-1 && y>=0 && y<=m[x]-1 && !st[x][y];`

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=210;

int g[N][N];

int st[N][N];

int n,m[N];

string s;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=n-1 && y>=0 && y<=m[x]-1 && !st[x][y];

}

void bfs(int x,int y){

	queue<PII> q;

	q.push({x,y});

	st[x][y]=true;

	while(q.size()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && g[nx][ny]==1){

				st[nx][ny]=true;

				q.push({nx,ny});

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	getline(cin,s);

	for(int i=0;i<n;i++){

		getline(cin,s);

		m[i]=s.size();

		for(int j=0;j<m[i];j++){

			if(isalpha(s[j])){

				g[i][j]=1;

			}

			else{

				g[i][j]=0;

			}

		}

	}

//	for(int i=0;i<n;i++){

//		for(int j=0;j<m[i];j++){

//			cout<<g[i][j];

//		}

//		cout<<endl;

//	}

	int cnt=0;

	for(int i=0;i<n;i++){

		for(int j=0;j<m[i];j++){

			if(g[i][j]==1 && !st[i][j]){

				bfs(i,j);

				cnt++;

			}

		}

	}

	cout<<cnt;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[UCV2013H - Slick|UCV2013H - Slick]] 🏠 [[00-刷题理模型]] ➡️ [[海战|海战]]